168

13

Useful Algorithms

13.5

The Maximum Entropy Method

Consider the problem of deducing the positions of stars and galaxies from a noisy map

of electromagnetic radiation intensity. One should have an estimate for the average

noise level: The simple treatment of such a map is to reject every feature greater than

the mean noise level and accept every one that is greater. Such a map is likely to be

a considerably distorted version of reality. ¹²

The maximum entropy method can be considered as a heuristic drill for applying

D. Bernoulli (1777) maxim: “Of all the innumerable ways of dealing with errors of

observation, one should choose the one which has the highest degree of probability

for the complex of observations as a whole”. In effect, it is a generalization of the

method of maximum likelihood.

First, the experimental map must be digitized both spatially and with respect to

intensity; that is, it is encoded as a finite set of pixels, each of which may assume

one of a finite number of density levels. Let that density be m Subscript jm j at the j jth pixel.

Then random maps are generated and compared with the data. All those inconsis-

tent with the data (with due regard to the observational errors) are rejected. The

commonest map remaining is then the most likely representation. ¹³ This process

is the constrained maximization of the configurational entropy minus sigma summation m Subscript j Baseline log m Subscript j−^Σ m j log m j (the

unconstrained maximization would simply lead to a uniform distribution of density

over the pixels). Maximum entropy image restoration yields maximum information

in Shannon’s sense. ¹⁴

References

Bernoulli D (1777) Diiudicatio maxime probabilis plurium observationem discrepantium atque

verisimillima inductio inde formanda. Acta Acad Sci Imp Petrop 1:3–23

Buck B, Macaulay VA (eds) (1991) Maximum entropy in action. Clarendon Press, Oxford

Good IJ (1962) Botryological speculations. In: Good IJ (ed) The scientist speculates. Heinemann,

London, pp 120–132

Gorban AN, Popova TG, Zinovyev A (2005) Codon usage trajectories and 7-cluster structure of

143 complete bacterial genomic sequences. Phys A 353:365–387

Graps A (1995) An introduction to wavelets. IEEE Comput Sci Eng 2:50–61

Gull SF, Daniell GJ (1978) Image reconstruction from incomplete and noisy data. Nat (Lond)

272:686–690

Kendall DG (1970) A mathematical approach to seriation. Philos Trans R Soc A 269:125–135

Kruskal JB (1964) Multidimensional scaling by optimizing goodness of fit to a nonmetric hypoth-

esis. Psychom 29:1–27

Skilling J, Bryan RK (1984) Maximum entropy image reconstruction: general algorithm. Mon Not

R Astron Soc 211:111–124

12 Implicitly, Platonic reality is meant here.

13 Gull and Daniell (1978).

14 See also Skilling and Bryan (1984); Buck and Macaulay (1991).